#pragma once

template <typename Key, typename Val>
class hMapNode
{
	struct FillDebugParam;
	friend struct hMapNode::FillDebugParam;

	static hMapNode _nil;
	static hMapNode* _pNil;

	hMap<Key, Val>* _owner = NULL;
	hMapNode* _parent = _pNil;
	hMapNode* _left = _pNil;
	hMapNode* _right = _pNil;

	bool _red = true;
	std::pair<const Key, Val>* _pData = NULL;
public:
	hMapNode(hMap<Key, Val>* pMap = NULL);

	enum TraverseType
	{
		TraverseType_Pre,
		TraverseType_Mid,
		TraverseType_Post,
	};

	enum RotateType
	{
		RotateType_Left,
		RotateType_Right,
	};

	enum NodeType
	{
		NodeType_Nil,
		NodeType_Root,
		NodeType_Left,
		NodeType_Right,
	};

	template<typename... Args>
	void emplaceCallback(Key k, Args... args);
	void eraseCallback(Key k);
	std::ostream& fillDebugCallback(std::ostream& os) const;

	const hMapNode* getNodeByHeight(uint8_t height, size_t idx) const;

	template <typename Callback>
	bool traverse(uint8_t type, Callback& cb);
	template <typename Callback>
	bool traverse(uint8_t type, Callback& cb) const;

	bool rotate(uint8_t type);

	hMapNode* getRoot();
	hMapNode* getUncle();
	hMapNode* getBrother();
	hMapNode* getMin();
	hMapNode* getMax();
	hMap<Key, Val>* getOwner();
	uint8_t getNodeType() const;
	uint8_t calcHeightMax() const;

	bool operator==(const hMapNode& node) const { return _parent == node._parent && _left == node._left && _right == node._right; }
	bool operator!=(const hMapNode& node) const { return !operator==(node); }
private:
	bool rotateParent();
	bool rotateLeft();
	bool rotateRight();

	bool emplaceFixup();
	bool checkNeedEmplaceFixup();
	bool emplaceFixupCase1(hMapNode* pGrandpa, hMapNode* pUncle);
	bool emplaceFixupCase2(hMapNode* pParent);
	bool emplaceFixupCase3();

	bool transplant(hMapNode* pNode);
	bool eraseFixup();
	bool eraseFixupCase1(hMapNode*& pBrother);
	bool eraseFixupCase2(hMapNode* pBrother);
	bool eraseFixupCase3(hMapNode*& pBrother, bool isLeft);
	bool eraseFixupCase4(hMapNode* pBrother, bool isLeft);
};

#include "hMapNodeImpl.h"